#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int makingChange(int amount, int limit, vector<int> coins){
    int result = 0;
    int coin = coins.back();
    coins.pop_back();

    if (coins.size() == 0) {
        if (amount / coin <= limit) {
            return 1;
        }
    }
    else{
        for (int i = 0; i <= amount / coin; ++i) {
            result += makingChange(amount - coin * i, limit - i, coins);
        }
    }
    return result;
}

int main(int argc, char const *argv[])
{
    int amount = 1000;
    int limit = 15;
    vector<int> coins{10, 50, 100, 500};

    cout << makingChange(amount, limit, coins) << endl;

    return 0;
}
